/*
 *  dag_loop_analyzer.cpp
 *  dag
 *
 *  Created by Phillip Popp on 3/6/11.
 *  Copyright 2011 __MyCompanyName__. All rights reserved.
 *
 */

#include "dag_loop_analyzer.h"
#include <list>
#include <set>
#include <stack>
#include <algorithm>

using namespace dag;
using namespace std;

		
Vertex::Vertex()
:	node(NULL),
	index(-1),
	lowIndex(-1)
{
}
			
Vertex::Vertex(const Node* a_node)
:	node(a_node),
	index(-1),
	lowIndex(-1)
{
}
		
bool Vertex::hasBeenIndexed() const {
	return index != -1;
}
		
bool Vertex::operator==(const Vertex& rhs) const {
	return node == rhs.node;
}

bool Vertex::operator<(const Vertex& rhs) const {
	return node < rhs.node;
}

LoopAnalyzer::LoopAnalyzer()
:	m_Index(0),
	m_Graph(NULL)
{
}
	
LoopAnalyzer::~LoopAnalyzer() {
}
	
void LoopAnalyzer::findLoops(const Graph& graph, list<set<const Node*> >& loops) {
	reset();
	m_Graph = &graph;
	
	/* first check if there any nodes that loop unto themselves */
	const set<Node*>& nodes = graph.getNodes();
	set<Node*>::const_iterator nodeIter;
	for (nodeIter = nodes.begin(); nodeIter != nodes.end(); nodeIter++) {
		
		/* there shouldn't be any NULL nodes in there, but if there is, make
		 * sure not to check it.  It's not the responsibility of this analyzer
		 * to care whether nodes are NULL or not, hence no error is reported. */
		if (*nodeIter == NULL) {
			continue;
		}
		
		bool selfLoop = false;
		const vector<Edge*>& outEdges = graph.getOutputEdges(*nodeIter);
		const vector<Edge*>& inEdges = graph.getInputEdges(*nodeIter);
		
		for (size_t i = 0; i < outEdges.size(); i++) {
			if (outEdges[i] != NULL) {
				if (outEdges[i]->to == outEdges[i]->from) {
					selfLoop = true;
				}
			}
		}
		
		for (size_t i = 0; i < inEdges.size(); i++) {
			if (inEdges[i] != NULL) {
				if (inEdges[i]->to == inEdges[i]->from) {
					selfLoop = true;
				}
			}
		}
		
		/* if a self loop occured, add to loop list */
		if (selfLoop) {
			set<const Node*> nodeSet;
			nodeSet.insert(*nodeIter);
			loops.push_back(nodeSet);
		}
	}
	
	/* Use Tarjan's Strongly Connected Component algorithm to find loops */
	const Node* headNode = graph.getHeadNode();
	if (headNode == NULL) {
		/* We require a head node to perform this analysis */
		throw MissingHeadNode();
	}
	
	/* this will traverse graph finding all loop nodes */
	m_Visited[headNode] = Vertex(headNode);
	set<const Node*> mainLoop = strongConnection(m_Visited[headNode], loops);
	if (mainLoop.size() > 1) {
		loops.push_back(mainLoop);
	}
}
	
void LoopAnalyzer::reset() {
	m_Visited.clear();
	m_Graph = NULL;
	m_Index = 0;
}

set<const Node*> LoopAnalyzer::strongConnection(Vertex& vertex, 
										  list<set<const Node*> >& loops) {
	set<const Node*> stronglyConnected;
	
	if (!vertex.hasBeenIndexed()) {
		/* Set the depth index for vertex to the smallest unused index */
		vertex.index = m_Index;
		vertex.lowIndex = m_Index;
		m_Index++;
		
		m_Stack.push_front(&vertex);
		
		/* Consider children of this vertex */
		const vector<Edge*> outEdges = m_Graph->getOutputEdges(vertex.node);
		for (size_t i = 0; i < outEdges.size(); i++) {
			if (outEdges[i]->to != NULL) {
				if (m_Visited.count(outEdges[i]->to) == 0) {
					/* this node hasn't been visited yet, so recurse on it */
					m_Visited[outEdges[i]->to] = Vertex(outEdges[i]->to);
					set<const Node*> loopSet;
					loopSet = strongConnection(m_Visited[outEdges[i]->to], 
											   loops);
					vertex.lowIndex = min(vertex.lowIndex, 
										  m_Visited[outEdges[i]->to].lowIndex);
					
					/* if the loop set is greater than one, then this child is
					 * the root of a loop and should be added to the loop set */
					if (loopSet.size() > 1) {
						loops.push_back(loopSet);
					}
				}
				else if (count(m_Stack.begin(), 
							   m_Stack.end(), 
							   &m_Visited[outEdges[i]->to]) > 0) {
					/* the output edge is already in the stack, and is part of
					 * the current loop */
					vertex.lowIndex = min(vertex.lowIndex, 
										  m_Visited[outEdges[i]->to].index);
				}
			}			
		}
	
		/* check for strongly connected components */
		if (vertex.index == vertex.lowIndex) {
			while (m_Stack.front() != &vertex && m_Stack.size() > 0) {
				stronglyConnected.insert(m_Stack.front()->node);
				m_Stack.pop_front();
			}

			if (m_Stack.front() == &vertex) {
				stronglyConnected.insert(m_Stack.front()->node);
				m_Stack.pop_front();
			}
		}
	}
	return stronglyConnected;
}
